package com.company.array;

import java.util.*;

/**
 * @author jrue
 * @description https://leetcode-cn.com/problems/top-k-frequent-elements/
 * 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
 * @date 2019/11/14 10:51
 */
public class TopKFrequent {

    public static void main(String[] args) {
        List<Integer> list = topKFrequent(new int[]{4,1,-1,2,-1,2,3}, 2);
        list.forEach(e -> {
            System.out.println(e);
        });
    }

    public static List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i],map.getOrDefault(nums[i],0) + 1);
        }

        List<Integer> list = new ArrayList<>(k);
        for (int i = 0; i < k; i++) {
            Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
            int max = 0;
            int index = 0;
            for (Map.Entry<Integer, Integer> entry : entries) {
                if (entry.getValue() > max) {
                    max = entry.getValue();
                    index = entry.getKey();
                }
            }
            map.put(index,0);
            list.add(index);
        }

        return list;
    }

}
